package 简单.栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。
 * <p>
 * 给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
 * <p>
 * 注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
 * <p>
 * 返回可以通过分割得到的平衡字符串的 最大数量 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/split-a-string-in-balanced-strings
 */
public class 分割平衡字符串_1221 {

    public static void main(String[] args) {

        //RL   1
        /**
         * RL 2
         * RLRL  3
         * RLRLRL  4
         * LRRLRLRL
         */
        //RLRRLLRLRL
        System.out.println(balancedStringSplit2("RLLLLRRRLR"));

    }

    /**
     * 栈
     * 遇到和栈顶元素相同时入栈，不同时出栈，栈为空时，出现了平衡字符串
     *
     * @param s
     * @return
     */
    public static int balancedStringSplit(String s) {
        int ans = 0;
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            if (stack.isEmpty()) {
                stack.offerFirst(s.charAt(i));
                continue;
            }
            if (stack.peek() != s.charAt(i)) {
                stack.pollFirst();
            } else {
                stack.offerFirst(s.charAt(i));
            }
            if (stack.isEmpty()) {
                ans++;
            }
        }
        return ans;
    }

    /**
     * 用变量模拟栈
     * s中的R和L是数量相等的，随便指定一个入栈，另一个出栈，
     * 入栈只需增加数量即可，R和L的价值是相等的
     *
     * @param s
     * @return
     */
    public static int balancedStringSplit2(String s) {
        int ans = 0;
        int stack = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'R') {
                stack++;
            } else {
                stack--;
            }
            if (stack == 0) {
                ans++;
            }
        }
        return ans;
    }

}
